package com.ruoyi.learn.java.algorithm.graph;

import java.util.*;

public class DFSIterative {

    private Map<Integer, List<Integer>> graph;

    public DFSIterative() {
        graph = new HashMap<>();
    }

    public void addEdge(int u, int v) {
        graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    // 深度优先搜索（迭代，使用栈）
    public void dfsIterative(int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();

        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();

            if (!visited.contains(node)) {
                visited.add(node);
                System.out.print(node + " ");

                // 将所有未访问的邻居压入栈（逆序保证顺序一致）
                List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
                // 逆序添加，使得先访问编号小的节点（可选）
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int neighbor = neighbors.get(i);
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        DFSIterative dfs = new DFSIterative();

        dfs.addEdge(1, 2);
        dfs.addEdge(1, 3);
        dfs.addEdge(2, 4);
        dfs.addEdge(3, 5);
        dfs.addEdge(3, 6);

        System.out.println("迭代 DFS 遍历结果：");
        dfs.dfsIterative(1);
        System.out.println();
    }
}
